//
//  ProblemOffer28.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 28. 对称的二叉树
 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     1
    / \
   2   2
  / \ / \
 3  4 4  3
 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     1
    / \
   2   2
    \   \
    3    3
 示例 1：
     输入：root = [1,2,2,3,4,4,3]
     输出：true
 示例 2：
     输入：root = [1,2,2,null,3,null,3]
     输出：false
 限制：0 <= 节点个数 <= 1000
 */
@objcMembers class ProblemOffer28: NSObject {
    func solution() {
        let root = TreeNode(1)
        root.left = TreeNode(2)
        root.left?.left = TreeNode(3)
        root.left?.right = TreeNode(4)
        
        root.right = TreeNode(2)
        root.right?.left = TreeNode(4)
        root.right?.right = TreeNode(3)
        print(isSymmetric(root))
        
        let root1 = TreeNode(1)
        root1.left = TreeNode(2)
        root1.left?.right = TreeNode(3)
        
        root1.right = TreeNode(2)
        root1.right?.right = TreeNode(3)
        print(isSymmetric(root1))
    }
    func isSymmetric(_ root: TreeNode?) -> Bool {
        if root == nil {
            return true
        }
        
        return isSymmetricDFS(root?.left, root?.right)
    }
    
    func isSymmetricDFS(_ l: TreeNode?, _ r: TreeNode?) -> Bool {
        if l == nil && r == nil {
            return true
        } else if l == nil || r == nil || l!.val != r!.val {
            return false
        }
        
        return isSymmetricDFS(l?.left, r?.right) && isSymmetricDFS(l?.right, r?.left)
    }
    
}
